package com.cuz.daileetcode.h100;

import com.cuz.daileetcode.utils.TreeNode;

import java.util.LinkedList;

public class P5 {

    public static void main(String[] args) {
        //[1,3,2,5,3,null,9]
        TreeNode t1 = new TreeNode(1);
        TreeNode t3 = new TreeNode(3);
        TreeNode t2 = new TreeNode(2);
        TreeNode t5 = new TreeNode(5);
        TreeNode t3y = new TreeNode(3);
        TreeNode t9 = new TreeNode(9);
        t1.left = t3;
        t1.right = t2;
        t3.left = t5;
        t3.right = t3y;
        t2.right = t9;

        System.out.println(new P5().widthOfBinaryTree(t1));
    }
    public int widthOfBinaryTree(TreeNode root) {
        if (root == null) {
            return 0;
        }

        LinkedList<TreeIndex> q = new LinkedList<>();
        q.addFirst(new TreeIndex(root, 1));
        int result = 1;
        // 1,3,2,5,3,n,9
        // 1,2,3,4,5,6,7
        while (!q.isEmpty()) {
            TreeIndex levelMin = q.getLast();
            TreeIndex levelMax = q.getFirst();
            result = Math.max(result, levelMax.index - levelMin.index + 1);

            int levelSize = q.size();
            while (levelSize > 0) {
                levelSize--;
                TreeIndex treeIndex = q.removeLast();
                int parentIndex = treeIndex.index;
                TreeNode parent = treeIndex.node;

                if (parent.left != null) {
                    q.addFirst(new TreeIndex(parent.left, 2 * parentIndex));
                }
                if (parent.right != null) {
                    q.addFirst(new TreeIndex(parent.right, 2 * parentIndex + 1));
                }
            }

        }

        return result;
    }

    static class TreeIndex {
        TreeNode node;
        int index;

        TreeIndex(TreeNode node, int index) {
            this.node = node;
            this.index = index;
        }
    }
}
